package com.icbc.DataStructuresAndAlgorithms;

import java.util.Arrays;

/**
 * 查找算法
 */
public class FindDomo {
	public static void main(String[] args) {
		int[] arr = {1,3,5,7,9,12,15};
		//String info = findErFen(arr, 0, arr.length - 1, 27);
		//System.out.println(info);
		//erfen(arr,11);
		System.out.println(feibonaqifind(arr, 2));
		
		
	}
	
	/**
	 * 功能: 二分查找法,仅适用于有序数组,递归方式
	 * @param arr	目标数组
	 * @param start	开始索引
	 * @param end	结束索引
	 * @param value	需要查找的值
	 * @return	查找的信息
	 */
	public static String findErFen(int[] arr, int start, int end, int value){
		System.out.println(1);
		//获取中间索引,用以进行二分查找
		int mid = start + (end - start) * (value - arr[start]) / (arr[end] - arr[start]);
		//int mid = (start + end) / 2;
		/*
		 * 这里是递归的退出条件,此处的递归有两个退出条件
		 * 1.当找到值时进行退出
		 * 2.当没有找到值时退出,但什么时候就是没有找到呢
		 * 		这里有start和end两个指针,当start == end
		 * 	时表示找的是那一个值,开始和结束都指向一个值,这时
		 * 	还不能结束,可能这一个值就是需要的值,只有当
		 * 	start > end 时才表示结束,没有找到,
		 * 	这里start和end在下面递归时都会进行+1和-1操作
		 */
		if (start > end){
			return "没有找到!";
		}
		
		/*
		 * 在升序的数组中当value > arr[mid]时,也就是查找的值大于中间值时,
		 * 这时应该在该数组的右边进行查找,而arr[mid]不是要找的值,那么在右递归时
		 * start就是mid + 1,end为结束
		 * 同理左递归也是一样
		 * 只有当value == arr[mid]时递归结束
		 */
		if (value > arr[mid]){
			//右递归
			return findErFen(arr,mid + 1,end,value);
		}else if (value < arr[mid]){
			//左递归
			return findErFen(arr,start,mid - 1,value);
		}else{
			//递归结束条件
			return "索引为:" + mid + "\n";
		}
	}
	
	//二分,非递归,其思路与递归的方式类似
	public static void erfen(int[] arr, int value){
		int start = 0;
		int end = arr.length - 1;
		int mid;
		while(true){
			mid = (start + end)/2;
			if (start > end){
				mid = -1;
				break;
			}
			
			if (value > arr[mid]){
				start = mid + 1;
			}else if(value < arr[mid]){
				end = mid -1;
			}else{
				break;
			}
		}
		System.out.println(mid);
	}
	
	//首先生成一个斐波那契的数组,根据此数组数据来寻找黄金分割点
	public static int[] fbnarr(int length){
		int[] arr = new int[length];
		arr[0] = 1;
		arr[1] = 1;
		for (int i = 2; i < arr.length; i++) {
			arr[i] = arr[i - 1] + arr[i - 2];
		}
		return arr;
	}
	/*
	 * 斐波那契查找法思路:
	 *		1.在斐波那契数组(fbn)中当前节点k的值等于它前面两个节点(k-1和k-2)的值之和
	 *	而fbn[k-1]值是fbn[k]值的黄金分割点,且fbn[k] = fbn[k - 1] + fbn[k - 2]
	 *		2.这时假设有一个数组arr,该数组的长度就是fbn[k]也就是说arr.length = fbn[k],
	 *	那么就可以将此数组分成两部分,也就是fbn[k - 1]长度的数组arr1和fbn[k - 2]长度
	 *	的数组arr2,但fbn[k - 1]明显是fbn[k]的黄金分割点,所以说arr1数组就是arr数组的
	 *	黄金分割点前面的部分,而arr1.length就是arr数组的黄金分割点mid,arr2是arr数组的
	 *	黄金分割点后面的部分了,但是由于数组的索引是从0开始的,所以这里的mid是需要-1的,
	 *	那么这样就可以得到数组arr的黄金分割点就是mid = arr1.length - 1,
	 *	而fbn[k - 1] = arr1.length,所以mid = fbn[k - 1] - 1
	 *		3.到这里需要注意,fbn[k - 1] - 1只是arr数组的黄金分割点,而由arr数组分出来
	 *	的arr1的黄金分割点呢,在这里arr1.length = fbn[k - 1] = fbn[k - 2] + fbn[k - 3]
	 *	这样就明显了,arr1数组的黄金分割点就是fbn[k - 2] - 1,而arr1是arr数组的左部分,可以
	 *	得知当使用黄金分割法查找到左部分时相比较arr数组的黄金分割点k的值明显多减了1,那么右递归呢?
	 *	arr2.length = fbn[k - 2] = fbn[k - 3] + fbn[k - 4];也就说明fbn[k - 3] - 1就是
	 *	数组arr2的黄金分割点了,相比上面arr数组的黄金分割点可以明显的看出k的值多减了2,但arr2是arr
	 *	数组的右部分所以arr2黄金分割点是arr1.length + fbn[k - 3] - 1,而arr的黄金分割点mid
	 *	就是arr1.length - 1所以arr2的黄金分割点就是mid + 1 + fbn[k - 3] - 1
	 *		4.推演到这里基本就得到
	 *			int mid = low + fbn[k - 1] - 1;
	 *			向左时需要进行k--,至于mid - 1是为了mid节点已经判断,不再需要
	 *			向右时则需要将low = mid + 1;并k -= 2;
	 */
	public static int feibonaqifind(int[] arr, int value){
		//定义起始节点
		int low = 0;
		//定义结束节点
		int max = arr.length - 1;
		//定义斐波那契数组的指针k
		int k = 0;
		//定义黄金分割点mid
		int mid = 0;
		//生成斐波那契数组
		int[] fbn = fbnarr(20);
		/*
		 * 获取该数组长度对应斐波那契数组的节点,用来跟
		 * 斐波那契数组生成对应,当数组长度正好等于斐波那契数组的一个值时
		 * 必须对该数组进行扩容,扩容到下一个斐波那契值长度,不然在下面时会出现索引越界
		 * 为什么数组的长度不能正好是一个斐波那契值呢?
		 * 这时因为当正好是一个斐波那契值时并且该值还是一个偶数时,
		 * 数组的最后一位元素就无法进行遍历了或者当查找一个比数组中都大的数时
		 * 由于一直进入的都是value > fbn[mid],执行k -= 2,k会一直减到0,再次循环就
		 * 数组越界了,但长度为奇数的数组不受影响
		 */
		while (max >= fbn[k] - 1){
			k ++;
		}
		/*
		 * 这里还是对上面的扩展,并且当原本的数组长度不够时需要对原本的数组进行扩容
		 * 在这里扩容有一个基准那就是数组长度是fbn[k] - 1个元素是不需要扩容,否则
		 * 其他情况都需要扩容,并且将扩容的数组多余部分值改为arr[max]
		 */
		int[] ints = arr;
		if (max < fbn[k] - 2) {
			ints = Arrays.copyOf(arr, fbn[k] - 1);
			for (int i = max + 1; i < ints.length; i++) {
				ints[i] = arr[max];
			}
		}
		//开始循环
		while (low <= max){
			//获取黄金分割点
			mid = low + fbn[k - 1] - 1;
			//当value < 黄金分割节点时,判断黄金分割点左边的数组,重新定义边界
			if (value < ints[mid]){
				//low保持不变,将max移动到黄金分割点左边
				max = mid - 1;
				//对k进行--,用来获取变化后的数组黄金分割点
				k --;
			} else if (value > ints[mid]){
				//同理,获取右边数组的黄金分割点及边界
				low = mid + 1;
				k -= 2;
			} else {
				//找到值时进行判断mid是否大于max,大于时返回max
				if (mid > max) {
					return max;
				} else {
					return mid;
				}
			}
		}
		//整个循环都没有走return 时,表示没有找到
		return -1;
	}
}
